/* *
* 堆排序是一种树形选择排序，基于堆数据结构，它的核心思想是利用堆这种数据结构，
* 首先将待排序的队列构建成一个大根堆或小根堆，
* 然后将堆顶元素与最后一个元素进行交换，然后将剩余的元素重新调整为一个堆，重复这个过程，直到整个序列有序
* 堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1) 不稳定
* 堆排的具体流程如下:
*  1.构建一个大根堆或小根堆；
*  2.将堆顶元素与最后一个元素进行交换；
*  3.重新调整剩余元素，使其重新构成一个大根堆或小根堆；
*  4.重复步骤2和步骤3，直到整个序列有序。
* 简单来说，堆排序就是不停地将最大或最小的元素与数组尾部元素交换，然后对剩余元素重新构建堆，重复这个过程，最终得到有序的数组
* */



function heapify(heap, i, len) {
    let max = i
    let left = 2 * i + 1
    let right = 2 * i + 2
    //? 左孩子存在且比根大
    if (left < len && heap[left] > heap[max]) {
        max = left
    }
    //? 右孩子存在且比根大
    if (right < len && heap[right] > heap[max]) {
        max = right
    }
    //? 最大值变了 更换值
    if (max !== i) {
        [heap[i], heap[max]] = [heap[max], heap[i]]
        //? 递归处理 (如根节点需要调整则必须比较整个下面的树进行调整，所以此处的递归是必须的)
        heapify(heap, max, len)
    }
}
const nums = [5,2,6,1,7,2,10,8]
//? 第一步 建立最大堆（升序）从最后一个非叶子节点开始
for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
    heapify(nums, i, nums.length)
}
//? 第二步 排序 一步步调整每个数
for (let i = nums.length - 1; i >= 0; i--) {
    //? 将尾叶子与根交换
    [nums[0], nums[i]] = [nums[i], nums[0]]
    //? 从头往下开始调整
    heapify(nums, 0, i)
    console.log(nums)
}
// console.log(nums)
